#! usr/bin/env python
#-*- coding: UTF-8 -*-

import sys
import grafo
import math
import heapq

def guardar_vertices(archivo, Grafo):
	'''Lee la cantidad de lineas equivalente a las intersecciones y
	agrega el vértice con el primer campo como id, y el resto como datos'''
	linea = archivo.readline()
	for i in range (int(linea)):
		linea = archivo.readline()
		campos = linea.split(',')
		v = grafo.Vertice(int(campos[0]),campos)
		Grafo.agregar_vertice(v) 

def guardar_aristas(archivo, Grafo):
	'''Lee la cantidad de lineas equivalente a las calles y
	agrega las aristas con la información correspondiente'''
	linea = archivo.readline()
	for i in range (int(linea)):
		linea = archivo.readline()
		campos = linea.split(',')
		v_inicial = Grafo.obtener_vertice(int(campos[4]))
		v_final = Grafo.obtener_vertice(int(campos[5]))
		Grafo.agregar_arista(v_inicial, v_final, campos)
		#Si es doble mano agrego la arista hacia el vértice final
		if ( int(campos[3]) == 0):
			Grafo.agregar_arista(v_final, v_inicial, campos)

def cargar_grafo(Grafo, archivo):
	'''Dado un archivo con los datos de los vértices y aristas, lo abre y lee linea a linea
	guardando en el grafo la información correspondiente'''
	
	try:
		archivo = open(archivo, "r")
	
	except IOError:
		print "Archivo inexistente"
		sys.exit()
	
	guardar_vertices(archivo,Grafo)
	guardar_aristas(archivo,Grafo)
	
	archivo.close()
	return True


def mejor_camino(vert_origen, vert_destino, g, limite):
	'''Calcula el mejor camino entre dos vértices mediante el algoritmo
	de Dijstra. Devuelve un diccionario con las distancias y otro con
	los caminos. Si se ingresó un valor de distancia máximo (límite) y la distancia
	entre vértices lo supera, el diccionario de caminos no contendrá al vértice destino.'''
	
	if (not vert_origen) or (not vert_destino):
		return ({},{})
	#2 = posición del valor "peso" (tipo de calle) en la lista de datos de la arista que sale del vértice.
	#datos = [calle1,nombre,tipo de calle, mano única, nodo inicial, nodo final]
	return  dijkstra(g, vert_origen, vert_destino, 2, limite)


def coordenadas_ruta(caminos,origen, destino):
	'''Obtiene las coordenadas de los vértices en la ruta hasta llegar
	a destino y las devuelve en una cadena'''
	coordenadas = []
	coordenadas.append(origen.datos[3])
	coordenadas.append((origen.datos[4]).replace('\n',' '))
	if not caminos.has_key(destino):
		#en el caso que no haya camino, por ej si se restringió la distancia
		#devuelve una cadena vacía para escribir espacio en blanco en el archivo de rutas
		return " "
	for vertice in caminos[destino]:
		coordenadas.append(vertice.datos[3])
		coordenadas.append((vertice.datos[4]).replace('\n',' '))
	
	coordenadas = ",".join(coordenadas)
	return coordenadas
	

def crear_archivo_rutas(origen):
	'''Crea un nuevo archivo "rutas.kml" donde se escribirán todos los caminos.
	Escribe un encabezado y las coordenadas del origen (pizzeria) '''
	try:
		arch_rutas = open("rutas.kml", "w")
	except IOError:
		print "Error al crear el archivo\n"
		sys.exit()
	
	#Escribo en el archivo el título , encabezado y coordenadas de la pizzería
	
	encabezado = """<?xml version="1.0" encoding="UTF-8"?>
<kml xmlns="http://www.opengis.net/kml/2.2" xmlns:gx="http://www.google.com/kml/ext/2.2" xmlns:kml="http://www.opengis.net/kml/2.2" xmlns:atom="http://www.w3.org/2005/Atom">
<Document>\n\n\n"""
	arch_rutas.write(encabezado)
	
	titulo = "\n\t<name> CAMINOS </name>\n"
	arch_rutas.write(titulo)
	
	#Escribo el marcador de la pizzería
	marcador_origen = """	\n<Placemark>
		<name>Pizzería</name>
		<Point>
			<coordinates>""",origen.datos[3],origen.datos[4],"""</coordinates>
		</Point>
	</Placemark>\n"""
	marcador_origen = " ".join(marcador_origen)
	arch_rutas.write(marcador_origen)
	
	arch_rutas.close()


def agregar_pie_arch_rutas():
	'''Agrega el pie al archivo_rutas.kml'''
	try:
		arch_rutas = open("rutas.kml", "a+")
	except IOError:
		print "Error al abrir el archivo\n"
		sys.exit()
	pie = """\n</Document>
</kml>"""
	arch_rutas.write(pie)
	arch_rutas.close()
	
def escribir_ruta_en_archivo(caminos,origen,destino):
	'''Escribe en un archivo la ruta desde el origen hacia el destino'''
	try:
		arch_rutas = open("rutas.kml", "a+")
	except IOError:
		print "Error al abrir el archivo\n"
		sys.exit()

	coordenadas= coordenadas_ruta(caminos,origen, destino)
	

	linea= ["""	\n<Placemark>
		<name>Marche una grande de muzza</name>
		<LineString>
			<coordinates>\n""",coordenadas, """		\n</coordinates>
		</LineString>
	</Placemark>\n"""]

	linea = " ".join(linea)
		
	marcador_destino = """\n	<Placemark>
		<name>Cliente</name>
		<Point>
			<coordinates>""",destino.datos[3],destino.datos[4],"""</coordinates>
		</Point>
	</Placemark>\n"""
	marcador_destino = " ".join(marcador_destino)
	

	arch_rutas.write(linea)
	arch_rutas.write(marcador_destino)
	arch_rutas.close()

def obtener_vertice(grafo):
	'''Devuelve el vértice correspondiente a la intersección de calles
	ingresada por el usuario, si no existe la intersección se vuelve a pedir
	el ingreso de la dirección'''
	vertice = obtener_interseccion(grafo)
	while not vertice:
		print "Intersección inválida"
		vertice = obtener_interseccion(grafo)
	return vertice

def obtener_interseccion(grafo):
	'''Pide el ingreso los nombres de dos calles, busca en el grafo el objeto vértice
	cuyas aristas tengan el nombre de ambas calles, si lo encuentra lo devuelve
	sino devuelve None'''
	calle1 = raw_input("Ingrese primer calle que genera la intersección:\n")
	calle2 = raw_input("Ingrese la segunda calle que genera la intersección:\n")
	calles= []
	for vertice_id in grafo.vertices.keys():
		vertice = grafo.obtener_vertice(vertice_id)
		aristas = grafo.aristas(vertice)
		for arista in aristas:
			datos = arista[1]  #arista = (vertice, datos)
			calles.append(datos[1])   #datos = (calle, nombre, tipo, mano, n_ini, n_fin)
		if calle1 in calles:
			if calle2 in calles:
				return vertice
		calles = []
	return None
		

def distancia_entre_puntos(x1,x2,y1,y2):
	'''Calcula la distancia entre dos puntos'''
	return math.sqrt((x1-y1)**2+(x2-y2)**2)


def dijkstra(grafo, origen, destino=None, p=0, limite = None):
	'''Devuelve un diccionario con las distancias entre origen y destino
	y otro diccionario con los caminos entre ellos. Límite es un valor ingresado por el usuario
	el cual representa la distancia máxima que se puede recorrer. p es la posición del valor peso
	en la lista de datos de la arista'''
	if origen == destino: return (0, [origen])
	distancias = {}  # diccionario con las distancias finales
	caminos = {}  # diccionario de caminos
	pesos = {}
	heap = [] # usa heapq con tuplas de (distancia,nodo)
	heapq.heappush(heap,(0,origen, []))
	padre = origen
	while heap:
		(peso,vert,camino)=heapq.heappop(heap)
		if vert in pesos: continue # ya está listo
		pesos[vert] = peso
		caminos[vert] = camino
		distancias[vert] = distancia_entre_puntos(float(vert.datos[1]), float(vert.datos[2]),float(padre.datos[1]), float(padre.datos[2]))
		if vert == destino: break # Si ya llegue salgo
		for dest, datos in grafo.aristas(vert):
			v_peso = pesos[vert] + int(datos[p]) #p = posición del valor peso en lista de datos de la arista
			camino = caminos[vert]+[dest]
			padre = vert
			if limite and distancias[vert] > limite:
				continue
			else:
				heapq.heappush(heap,(v_peso, dest, camino))
	return (pesos, distancias,caminos)

def informar_distancia(distancias, destino):
	'''Informa si se puede llegar o no a destino, en caso que se pueda llegar
	imprime la distancia hasta destino'''
	if not distancias.has_key(destino):
		print "No se puede llegar a destino\n"
	else:
		print "Distancia:" ,distancias[destino]

def main():
	if len(sys.argv) < 2:
		print "Error: Cantidad de parámetros incorrecta\n"
		sys.exit()
	#argv1 = archivo de avellaneda	
	archivo = sys.argv[1]
	graph = grafo.Grafo()
	cargar_grafo(graph, archivo)
	print "DIRECCIÓN DE LA PIZZERÍA"
	vert_pizzeria = obtener_vertice(graph)
	crear_archivo_rutas(vert_pizzeria)
	
	seguir = "s"
	while (seguir != "n"):
		print "DIRECCIÓN DEL CLIENTE"
		vert_destino = obtener_vertice(graph)
		aux = raw_input("Restringir distancia? s/n: ")
		if aux == "s" or aux == "S":
			limite = input("Ingrese valor distancia máxima:\n ")
			pesos,distancias,caminos = mejor_camino(vert_pizzeria, vert_destino, graph,limite)
		else:
			pesos,distancias,caminos = mejor_camino(vert_pizzeria, vert_destino, graph, None)
		escribir_ruta_en_archivo(caminos,vert_pizzeria, vert_destino)
		informar_distancia(distancias, vert_destino)
		seguir = raw_input("Desea continuar(s/n)?\n")
	
	agregar_pie_arch_rutas()


main()
